Encryption and Decryption could be really easy, while we expected the decryption to be harder!

Files given:

• output.txt
• onlude.sage

def prepare(msg):
	A = zero_matrix(GF(p), 11, 11)
	for k in range(len(msg)):
		i, j = 5*k // 11, 5*k % 11
		A[i, j] = cross(msg[k])
	return A

def keygen():
	R = random_matrix(GF(p), 11, 11)
	while True:
		S = random_matrix(GF(p), 11, 11)
		if S.rank() == 11:
			_, L, U = S.LU()
			return R, L, U

def encrypt(A, key):
	R, L, U = key
	S = L * U
	X = A + R
	Y = S * X
	E = L.inverse() * Y
	return E

A = prepare(flag)
key = keygen()
R, L, U = key
S = L * U
E = encrypt(A, key)
print(f'E = \n{E}')
print(f'L * U * L = \n{L * U * L}')
print(f'L^(-1) * S^2 * L = \n{L.inverse() * S**2 * L}')
print(f'R^(-1) * S^8 = \n{R.inverse() * S**8}')

A contains our flag and we are given where is the LU-decomposition. The flag is also encrypted in a matrix that would be trivial to decrypt once we know what is.

Obtaining is easy:

In order to solve for and finally , we consider the eigendecomposition of , then . We can compute easily and to get , we simply square root each term and brute force all possible combination of signs, possibilities here. Eventually one of those would allow us to decrypt and give us the flag.

Solution at solve.sage